package tree

import (
	"fmt"
	"strconv"
)

// 以下代码不用提交
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 构建树
// 如: 3,9,20,null,null,15,7 ，构建结果:
/*
           3
     	9     20
   null null 15 7
*/
func BuildTreeNode(arr []string) *TreeNode {
	rootInt, _ := strconv.Atoi(arr[0])
	root := &TreeNode{
		Val: rootInt,
	}
	index := 1
	nodeArr := []*TreeNode{root}
	for index < len(arr) {
		//len := len(nodeArr)
		tempNodeArr := make([]*TreeNode, 0)
		for _, currentNode := range nodeArr {
			var left, right *TreeNode
			if nil == currentNode {
				// 空节点的下面也一定都是空节点
				left, right = nil, nil
			} else {
				leftValStr, rightValStr := arr[index], arr[index+1]
				left, right = nodeValStrToNode(leftValStr), nodeValStrToNode(rightValStr)
				currentNode.Left, currentNode.Right = left, right
			}
			tempNodeArr = append(tempNodeArr, left, right)
			index += 2
		}
		nodeArr = tempNodeArr
	}
	return root
}

func nodeValStrToNode(str string) *TreeNode {
	if "null" == str {
		return nil
	} else {
		retInt, _ := strconv.Atoi(str)
		return &TreeNode{
			Val: retInt,
		}
	}
}

// 输出树结构
// 格式: [3] [9, 20] [null null 15 7]
func PrintTreeNode(node *TreeNode) {
	if nil == node {
		fmt.Println("null tree")
	}
	lastLevelNumArr := []string{strconv.Itoa(node.Val)}
	lastLevelNodeArr := []*TreeNode{node}
	fmt.Printf("%v", lastLevelNumArr)

	for {
		isAllNull := true
		currentLevelNodeArr := make([]*TreeNode, 0)
		currentLevelNumArr := make([]string, 0)
		for _, currentNode := range lastLevelNodeArr {
			// 当前节点为空，直接往下塞入两个空节点
			if nil == currentNode {
				currentLevelNodeArr = append(currentLevelNodeArr, nil)
				currentLevelNodeArr = append(currentLevelNodeArr, nil)
				currentLevelNumArr = append(currentLevelNumArr, "null")
				currentLevelNumArr = append(currentLevelNumArr, "null")
				continue
			}
			currentLevelNodeArr = append(currentLevelNodeArr, currentNode.Left)
			currentLevelNodeArr = append(currentLevelNodeArr, currentNode.Right)

			if nil != currentNode.Left {
				isAllNull = false
				currentLevelNumArr = append(currentLevelNumArr, strconv.Itoa(currentNode.Left.Val))
			} else {
				currentLevelNumArr = append(currentLevelNumArr, "null")
			}

			if nil != currentNode.Right {
				isAllNull = false
				currentLevelNumArr = append(currentLevelNumArr, strconv.Itoa(currentNode.Right.Val))
			} else {
				currentLevelNumArr = append(currentLevelNumArr, "null")
			}
		}

		if isAllNull {
			break
		}
		lastLevelNodeArr = currentLevelNodeArr
		fmt.Printf(" %v", currentLevelNumArr)
	}

	fmt.Println()
}

// 测试树构造、输出方法
func TestTree() {
	treeArr := []string{"3", "9", "20", "null", "null", "15", "7"}
	node := BuildTreeNode(treeArr)
	PrintTreeNode(node)
}
